#!/usr/bin/python
# -*- coding: utf-8 -*-

"""Project Euler Solution 065

Copyright (c) 2011 by Robert Vella - robert.r.h.vella@gmail.com

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
"""

import cProfile
from euler.numbers.decimal_base import integer_to_digits
from euler.numbers.fractions import QuickFraction


def get_answer():
    """Question:
    
    The square root of 2 can be written as an infinite continued fraction.
    2**0.5 = 1 + ____________1______
             2 + _________1_____
                 2 + ______1____   
                     2 + ___1___
                         2 + ...
    
    The infinite continued fraction can be written, 
    2**0.5 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In 
    a similar way, 23**0.5 = [4;(1,3,1,8)].
    
    It turns out that the sequence of partial values of continued fractions for
    square roots provide the best rational approximations. Let us consider the 
    convergents for 2**0.5.
    
    1 + 1 = 3/2
        2
         
    1 +__1__ = 7/5
       2 + 1    
           2
         
    1 +__1_____ = 17/12
       2 +__1__    
          2 + 1
              2
             
    1 +__1________ = 41/29
       2 +__1_____    
          2 +__1__
             2 + 1
                 2
    
    Hence the sequence of the first ten convergents for 2**0.5 are:
    1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 
    3363/2378, ...
    
    What is most surprising is that the important mathematical constant,
    e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].
    
    The first ten terms in the sequence of convergents for e are:
    2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...
    
    The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.
    
    Find the sum of digits in the numerator of the 100th convergent of the 
    continued fraction for e.
    """

    def get_sequence_element_at(n):
        """Return f[n] where f = [2,1,2,1,1,4,1,1,6,1,...]."""
        
        if n == 1:
            return 2
        elif n % 3 == 0:
            return n / 3 * 2
        else:
            return 1
        
    
    def get_e_covergent_at(n):
        """Return the [n]th e convergent, with n = 1 being the first 
        convergent.
        """
        
        #Solve the infinite continued fraction:
        #e_conver(n) = e_el(n - k) + _______________1_______________+__________
        #                            e_el(n - (k - 1)) +_________1_____________
        #                                               e_el(n - (k - 2)) + ...
        #Where k = n - 1, and e_el = [2,1,2,1,1,4,1,1,6,1,...]
        #                                                 
        convergent = QuickFraction(get_sequence_element_at(n), 1)
        
        while(n > 1):   
            convergent = 1 / convergent
            
            n -= 1
            
            convergent += get_sequence_element_at(n)
                   
        #Return the result.           
        return convergent
    
    #Return the result.
    return sum(integer_to_digits(get_e_covergent_at(100).numerator))
    
if __name__ == "__main__":
    cProfile.run("print(get_answer())")
